import random


# 冒泡算法、沉底算法 从大到小排序,最小值慢慢沉底到底部
def bubble_sort(seq):
    n = len(seq)
    for i in range(n - 1):
        print(seq)
        for j in range(n - i - 1):  # 最开始交换n-1次，n-2次，n-3次
            if seq[j] < seq[j + 1]:
                seq[j], seq[j + 1] = seq[j + 1], seq[j]
    print(seq)


# 选择排序，从大到小排序max
def select_sore(seq):
    n = len(seq)
    for i in range(0, n - 1):
        print(seq)
        max_value = seq[i]  # 假设该值为最大值
        max_index = i
        for j in range(i + 1, n):  # 获取剩余的最大值
            if seq[j] > max_value:
                max_value = seq[j]
                max_index = j
        seq[i], seq[max_index] = seq[max_index], seq[i]
    print(seq)


# 插入排序
def insertion_sore(seq):
    n = len(seq)
    for i in range(1, n):  # 一部分一部分的排序
        value = seq[i] # 保存当前位置的值，因为转移的过程中它的位置可能被覆盖
        # 找到这个值的合适位置，使得前边的数组有序 [0,i] 有序
        index = i
        while index > 0 and value > seq[index - 1]:
            seq[index] = seq[index - 1]
            index -= 1
        seq[index] = value
    print(seq)


if __name__ == '__main__':
    seq = list(range(10))
    random.shuffle(seq)

    seq1 = seq.copy()
    bubble_sort(seq1)
    print("*" * 30)

    seq2 = seq.copy()
    select_sore(seq2)
    print("*" * 30)

    seq3 = seq.copy()
    insertion_sore(seq3)
    print("*" * 30)
